package Sort;

import java.util.Arrays;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}21:19
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {4,3,2,5,1,8,9,10};
        sort(arr,0,arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr,int left,int right){
        int l = left;
        int r = right;
        int mid = (left + right) / 2;
        int indexValue = arr[mid];
        while (l < r){
            while (arr[l] < indexValue){
                l++;
            }

            while (arr[r] > indexValue){
                r--;
            }
            if (l >= r){
                break;
            }
            int temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;

            if (arr[l] == mid){
                r--;
            }

            if (arr[r] == mid){
                l++;
            }
        }
        if (l == r){
            l++;
            r--;
        }

        if (left < r){
            sort(arr,left,r);
        }
        if (right > l ){
            sort(arr,l,right);
        }
    }
}
